TNotes.leetcode

Appearance

0058. 最后一个单词的长度【简单】

0058. 最后一个单词的长度【简单】 ​

1. 📝 题目描述 ​

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。

单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

子字符串是字符串中连续的非空字符序列。

示例 1：

输入：s = "Hello World"
输出：5

解释：最后一个单词是“World”，长度为 5。

示例 2：

输入：s = "   fly me   to   the moon  "
输出：4

解释：最后一个单词是“moon”，长度为 4。

示例 3：

输入：s = "luffy is still joyboy"
输出：6

解释：最后一个单词是长度为 6 的“joyboy”。

提示：

  • 1 <= s.length <= 10^4
  • s 仅有英文字母和空格 ' ' 组成
  • s 中至少存在一个单词

2. 🎯 s.1 - 倒序扫描 ​

c
int lengthOfLastWord(char* s) {
    int i = 0;
    while (s[i] != '\0') {
        i++;
    }
    i--;

    while (i >= 0 && s[i] == ' ') {
        i--;
    }

    int length = 0;
    while (i >= 0 && s[i] != ' ') {
        length++;
        i--;
    }

    return length;
}
js
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function (s) {
  let length = 0
  let i = s.length - 1

  // 跳过尾部的空格
  while (i >= 0 && s[i] === ' ') {
    i--
  }

  // 计算最后一个单词的长度
  while (i >= 0 && s[i] !== ' ') {
    length++
    i--
  }

  return length
}
py
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        i = len(s) - 1

        while i >= 0 and s[i] == " ":
            i -= 1

        length = 0
        while i >= 0 and s[i] != " ":
            length += 1
            i -= 1

        return length
  • 时间复杂度：O(n)，其中 n 是字符串长度，最坏情况下需要从右向左扫描整个字符串
  • 空间复杂度：O(1)，只使用了常数级别的额外空间

算法思路：

  • 从字符串末尾开始倒序遍历，先跳过最后一个单词右侧可能存在的空格
  • 找到最后一个单词的末尾后，继续向左统计连续非空格字符的数量
  • 一旦遇到空格或越界，说明最后一个单词已经完整扫描完，累计的字符数就是答案

3. 🎯 s.2 - 去首尾空格 + 分词 ​

c
int lengthOfLastWord(char* s) {
    int left = 0;
    int right = 0;
    while (s[right] != '\0') {
        right++;
    }
    right--;

    while (s[left] == ' ') {
        left++;
    }
    while (right >= 0 && s[right] == ' ') {
        right--;
    }

    int trimmedLength = right - left + 1;
    char* trimmed = (char*)malloc(sizeof(char) * (trimmedLength + 1));
    for (int i = 0; i < trimmedLength; i++) {
        trimmed[i] = s[left + i];
    }
    trimmed[trimmedLength] = '\0';

    int lastLength = 0;
    char* token = strtok(trimmed, " ");
    while (token != NULL) {
        lastLength = strlen(token);
        token = strtok(NULL, " ");
    }

    free(trimmed);
    return lastLength;
}
js
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function (s) {
  return s.trim().split(/\s+/).pop().length
}
py
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.strip().split()[-1])
  • 时间复杂度：O(n)，其中 n 是字符串长度，裁剪首尾空格和分词都需要线性处理字符串
  • 空间复杂度：O(n)，需要为裁剪后的字符串或分词结果分配线性额外空间

算法思路：

  • 先去掉字符串首尾的空格，避免最后一个单词右侧的空格干扰结果
  • 再按连续空格将字符串拆分成若干单词
  • 由于最后一个单词一定是分词结果中的最后一个元素，直接取出它并返回长度即可

Discussions